#include <linux/sched.h>
#include <linux/kernel.h>
#include <linux/errno.h>
#include <linux/types.h>
#include <linux/ioport.h>
#include <linux/mm.h>
#include <linux/smp.h>
#include <linux/smp_lock.h>
#include <linux/stddef.h>
#include <linux/slab.h>
#include <asm/uaccess.h>

int get_depth(task_t* p) {
	// the root of the process tree (init) returns 0.
	int ret = 0;
	int i = 0;
	while (p->pid != 1 && i < 10) {
		i++;
		ret++;
		p = p->p_pptr;
	}
	return ret;
}



task_t* proc_climb(task_t* p, int delta) {
	int i;
	for (i = 0;i < delta; i++) {
		p = (p)->p_pptr;
	}
	return p;
}

task_t* get_common_ancestor(task_t *p1, task_t *p2) {
	int p1_depth, p2_depth;
	p1_depth = get_depth(p1);
	p2_depth = get_depth(p2);
	int delta = abs(p1_depth - p2_depth);
	if (p1_depth > p2_depth) {
		p1 = proc_climb(p1,delta);
	}
	else if (p2_depth > p1_depth) {
		p2  = proc_climb(p2,delta);
	}
	while (p1 != p2) {
		p1 = p1->p_pptr;
		p2 = p2->p_pptr;
	}
	return p1;
}

asmlinkage int sys_get_common_ancestor(int pid1, int pid2)
{
	int error, p1_depth, p2_depth;
	task_t *proc_p1, *proc_p2;
	task_t **tmp_proc;
	proc_p1 = find_task_by_pid(pid1);
	proc_p2 = find_task_by_pid(pid2);
	
	if (!proc_p1 || !proc_p2) {
		return -ESRCH;
	}
	return get_common_ancestor(proc_p1,proc_p2)->pid;
}


asmlinkage int sys_get_path(int pid1, int pid2, int *userBuf, int size) {
	int error;
	int res = 0;

	task_t *proc_p1 = find_task_by_pid(pid1);
	task_t *proc_p2 = find_task_by_pid(pid2);
	
	if (!proc_p1 || !proc_p2) {
		return -ESRCH;
	}

	//checking all of EINVAL errors.
	if (size <=0 || !userBuf) {
		return -EINVAL;
	}
	int writeable = access_ok(VERIFY_WRITE,userBuf,size * sizeof(int));
	if (!writeable) {
		return -EINVAL;
	}

	task_t *ancestor = get_common_ancestor(proc_p1, proc_p2);
	
	int depth_ancestor = get_depth(ancestor);
	int depth_p1 = get_depth(proc_p1) - depth_ancestor;
	int depth_p2 = get_depth(proc_p2) - depth_ancestor;

	int requiredSize = depth_p1 + depth_p2 + 1;

	if(requiredSize>size)
	{
		return -ENOMEM;
	}

	int* localBuf = kmalloc(requiredSize * sizeof(*localBuf),0);
	if (!localBuf) {
		return -ENOMEM;
	}
	int idx = 0;
	int i;
	for(i=0; i<depth_p1; ++i)
	{
		localBuf[idx] = proc_p1->pid;
		proc_p1 = proc_p1->p_pptr;
		idx++;
	}
	localBuf[idx] = ancestor->pid;
	for(i=requiredSize-1; i>requiredSize-depth_p2-1; --i)
	{
		localBuf[i] = proc_p2->pid;
		proc_p2 = proc_p2->p_pptr;
	}
	

	res = requiredSize;
	
	int copyRes;
	copyRes = copy_to_user(userBuf, localBuf, requiredSize * sizeof(*localBuf));
	if (copyRes != 0)
	{
		res = -EINVAL;
	}

	kfree (localBuf);
	return res;
}
